class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 排序
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ret;

        // 题目中说明了intervals数组至少有一个元素
        int left = intervals[0][0], right = intervals[0][1], n = intervals.size();
        for(int i = 1; i < n; i++)
        {
            if(intervals[i][0] > right)
            {
                // 如果新到来的左边界 > 目前的右边界
                // 说明是另一个区间，此时添加结果集，并且更新当前区间
                ret.push_back({ left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
            else
            {
                // 如果新到来的左边界 <= 目前的右边界
                // 更新左右边界
                right = max(right, intervals[i][1]);
                left = min(left, intervals[i][0]);
            }
        }

        // 最后一组也要添加到结果集
        ret.push_back({ left, right});
        return ret;
    }
};